package leecode

func buildTree105(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 {
		return nil
	}
	var traversal func(preorder []int, inorder []int) (result *TreeNode)
	traversal = func(preorder []int, inorder []int) (result *TreeNode) {
		//如果前序数组为空 停止
		if len(preorder) == 0 {
			return
		}
		//那当中间节点
		result = &TreeNode{Val: preorder[0]}
		if len(preorder) == 1 {
			return
		}
		//寻找中序数组的切割点
		var temp int
		for i := 0; i < len(inorder); i++ {
			if inorder[i] == preorder[0] {
				temp = i
				break
			}
		}
		//切割中序数组
		leftInorder := inorder[:temp]
		rightInorder := inorder[temp+1:]
		//切割前序数组的第一个元素
		preorder = preorder[1:]
		//切割前序数组
		leftPreorder := preorder[:len(leftInorder)]
		rightPreorder := preorder[len(leftPreorder):]
		//拿到结果
		result.Left = traversal(leftPreorder, leftInorder)
		result.Right = traversal(rightPreorder, rightInorder)
		return
	}
	return traversal(preorder, inorder)
}
